0599. 两个列表的最小索引总和【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 暴力解法

1. 📝 题目描述

• leetcode

给定两个字符串数组 list1 和 list2，找到 索引和最小的公共字符串。

公共字符串 是同时出现在 list1 和 list2 中的字符串。

具有 最小索引和的公共字符串 是指，如果它在 list1[i] 和 list2[j] 中出现，那么 i + j 应该是所有其他 公共字符串 中的最小值。

返回所有 具有最小索引和的公共字符串。以 任何顺序 返回答案。

---

示例 1：

输入:
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"],
list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 唯一的公共字符串是 “Shogun”。

示例 2：

输入:
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"],
list2 = ["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 具有最小索引和的公共字符串是 “Shogun”，它有最小的索引和 = (0 + 1) = 1。

示例 3：

输入：
list1 = ["happy","sad","good"],
list2 = ["sad","happy","good"]
输出：["sad","happy"]
解释：有三个公共字符串：
"happy" 索引和 = (0 + 1) = 1.
"sad" 索引和 = (1 + 0) = 1.
"good" 索引和 = (2 + 2) = 4.
最小索引和的字符串是 "sad" 和 "happy"。

---

提示：

• 1 <= list1.length, list2.length <= 1000
• 1 <= list1[i].length, list2[i].length <= 30
• list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。
• list1 的所有字符串都是 唯一 的。
• list2 中的所有字符串都是 唯一 的。

2. 🎯 s.1 - 暴力解法

js（map）

/**
 * @param {string[]} list1
 * @param {string[]} list2
 * @return {string[]}
 */
var findRestaurant = function (list1, list2) {
  // 创建哈希表存储 list1 中字符串及其索引
  const map = new Map()
  for (let i = 0; i < list1.length; i++) {
    map.set(list1[i], i)
  }

  let minSum = Infinity
  const result = []

  // 遍历 list2 查找共同字符串
  for (let j = 0; j < list2.length; j++) {
    if (map.has(list2[j])) {
      const i = map.get(list2[j])
      const sum = i + j

      if (sum < minSum) {
        // 找到更小索引和，更新结果数组
        minSum = sum
        result.length = 0 // 清空原数组
        result.push(list2[j])
      } else if (sum === minSum) {
        // 索引和相等，添加到结果数组
        result.push(list2[j])
      }
    }
  }

  return result
}

js（双层循环）

/**
 * @param {string[]} list1
 * @param {string[]} list2
 * @return {string[]}
 */
var findRestaurant = function (list1, list2) {
  let minSum = Infinity
  const result = []

  // 双重循环查找共同元素
  for (let i = 0; i < list1.length; i++) {
    for (let j = 0; j < list2.length; j++) {
      // 如果找到相同元素
      if (list1[i] === list2[j]) {
        const sum = i + j

        if (sum < minSum) {
          // 找到更小索引和，更新结果数组
          minSum = sum
          result.length = 0 // 清空原数组
          result.push(list1[i])
        } else if (sum === minSum) {
          // 索引和相等，添加到结果数组
          result.push(list1[i])
        }
        // 由于是从前往后遍历，后面的 j 值只会更大，
        // 再继续查已经没有意义了，可以提前结束内层循环。
        break
      }
    }
  }

  return result
}

• 时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别是 list1 和 list2 的长度。
• 空间复杂度：$O(m)$，用于哈希表存储 list1 的元素索引。